package binary_tree.Leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断是否为完全二叉树
 */
public class Num958_CompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        //判断当前所处的状态
        boolean isSecondStep=false;
        while (!queue.isEmpty()){
             TreeNode cur=queue.poll();
            if(!isSecondStep){
                //此时处在第一状态
                if (cur.left!=null&&cur.right!=null){
                    //左子树和右子树都不为空
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if(cur.left!=null){
                    //左子树为空切换为第二个状态
                    isSecondStep=true;
                    queue.offer(cur.left);
                }else if(cur.right!=null){
                    //只有右子树没有左子树 反例
                    return false;
                }else {
                    //出现第一个叶子结点
                    isSecondStep=true;
                }
            }else {
                //此时处在第二状态，所有节点必须是叶子结点 找到一个反例不是完全二叉树
                if(cur.left!=null||cur.right!=null){
                    return false;
                }

            }
        }
        return true;
    }
}
